package leet131palidromepartition

// 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
// 返回 s 所有可能的分割方案。
// 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

func isPalidrome(target []byte) bool {
	if len(target) == 0 {
		return true
	}

	for left, right := 0, len(target)-1; left <= right; left, right = left+1, right-1 {
		if target[left] != target[right] {
			return false
		}
	}
	return true
}

func PalindromePartition(target string) [][]string {
	// 思路：
	// 抽象为一个找组合元素的子问题：从给定子串中按照位置1/2/3...分别切割，将切割出来的元素添加到集合中。如果该元素不是回文串，就直接return即可，如果切割到最后了就添加到最终集合之中。
	var result [][]string
	var path []string
	var iterate func(start int) // start 是子串的开始位置
	iterate = func(start int) {
		// 出口就是我们的目标自己已经是空了
		if start == len(target) {
			pathCopy := make([]string, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)
			return
		}
		// 对每个子串都分别进行逐步增大的切割，步长分别为1、2、3直到len(substring)
		subtarget := target[start:]
		for i := 0; i < len(subtarget); i++ {
			// 此处的i是步长，表示切割1个、2个、3个字符...
			// 如果基于当前步长得到的子串不是回文串的话，则放弃
			maybetarget := string(subtarget[0 : i+1])
			if !isPalidrome([]byte(maybetarget)) {
				continue
			}
			path = append(path, maybetarget)
			iterate(start + i + 1) // 从新子串中找目标,注意新子串是当前循环中已经切割好的剩余部分...
			// 基于如上新子串找完回来之后，继续恢复到之前的未切割状态，准备添加下一次循环的切割元素
			path = path[:len(path)-1]
		}
	}
	iterate(0)
	return result
}
